// Problem 096: Sudoku

package main

import (
	"fmt"
)

var (
	cell    [81]uint16
	trials  [81 * 18]uint16
	tryCell int
)

func p096() {
	ans := 0
	loadSudoku("003020600900305001001806400008102900700000008006708200002609500800203009005010300")
	solve(&ans)
	loadSudoku("200080300060070084030500209000105408000000000402706000301007040720040060004010003")
	solve(&ans)
	loadSudoku("000000907000420180000705026100904000050000040000507009920108000034059000507000000")
	solve(&ans)
	loadSudoku("030050040008010500460000012070502080000603000040109030250000098001020600080060020")
	solve(&ans)
	loadSudoku("020810740700003100090002805009040087400208003160030200302700060005600008076051090")
	solve(&ans)
	loadSudoku("100920000524010000000000070050008102000000000402700090060000000000030945000071006")
	solve(&ans)
	loadSudoku("043080250600000000000001094900004070000608000010200003820500000000000005034090710")
	solve(&ans)
	loadSudoku("480006902002008001900370060840010200003704100001060049020085007700900600609200018")
	solve(&ans)
	loadSudoku("000900002050123400030000160908000000070000090000000205091000050007439020400007000")
	solve(&ans)
	loadSudoku("001900003900700160030005007050000009004302600200000070600100030042007006500006800")
	solve(&ans)
	loadSudoku("000125400008400000420800000030000095060902010510000060000003049000007200001298000")
	solve(&ans)
	loadSudoku("062340750100005600570000040000094800400000006005830000030000091006400007059083260")
	solve(&ans)
	loadSudoku("300000000005009000200504000020000700160000058704310600000890100000067080000005437")
	solve(&ans)
	loadSudoku("630000000000500008005674000000020000003401020000000345000007004080300902947100080")
	solve(&ans)
	loadSudoku("000020040008035000000070602031046970200000000000501203049000730000000010800004000")
	solve(&ans)
	loadSudoku("361025900080960010400000057008000471000603000259000800740000005020018060005470329")
	solve(&ans)
	loadSudoku("050807020600010090702540006070020301504000908103080070900076205060090003080103040")
	solve(&ans)
	loadSudoku("080005000000003457000070809060400903007010500408007020901020000842300000000100080")
	solve(&ans)
	loadSudoku("003502900000040000106000305900251008070408030800763001308000104000020000005104800")
	solve(&ans)
	loadSudoku("000000000009805100051907420290401065000000000140508093026709580005103600000000000")
	solve(&ans)
	loadSudoku("020030090000907000900208005004806500607000208003102900800605007000309000030020050")
	solve(&ans)
	loadSudoku("005000006070009020000500107804150000000803000000092805907006000030400010200000600")
	solve(&ans)
	loadSudoku("040000050001943600009000300600050002103000506800020007005000200002436700030000040")
	solve(&ans)
	loadSudoku("004000000000030002390700080400009001209801307600200008010008053900040000000000800")
	solve(&ans)
	loadSudoku("360020089000361000000000000803000602400603007607000108000000000000418000970030014")
	solve(&ans)
	loadSudoku("500400060009000800640020000000001008208000501700500000000090084003000600060003002")
	solve(&ans)
	loadSudoku("007256400400000005010030060000508000008060200000107000030070090200000004006312700")
	solve(&ans)
	loadSudoku("000000000079050180800000007007306800450708096003502700700000005016030420000000000")
	solve(&ans)
	loadSudoku("030000080009000500007509200700105008020090030900402001004207100002000800070000090")
	solve(&ans)
	loadSudoku("200170603050000100000006079000040700000801000009050000310400000005000060906037002")
	solve(&ans)
	loadSudoku("000000080800701040040020030374000900000030000005000321010060050050802006080000000")
	solve(&ans)
	loadSudoku("000000085000210009960080100500800016000000000890006007009070052300054000480000000")
	solve(&ans)
	loadSudoku("608070502050608070002000300500090006040302050800050003005000200010704090409060701")
	solve(&ans)
	loadSudoku("050010040107000602000905000208030501040070020901080406000401000304000709020060010")
	solve(&ans)
	loadSudoku("053000790009753400100000002090080010000907000080030070500000003007641200061000940")
	solve(&ans)
	loadSudoku("006080300049070250000405000600317004007000800100826009000702000075040190003090600")
	solve(&ans)
	loadSudoku("005080700700204005320000084060105040008000500070803010450000091600508007003010600")
	solve(&ans)
	loadSudoku("000900800128006400070800060800430007500000009600079008090004010003600284001007000")
	solve(&ans)
	loadSudoku("000080000270000054095000810009806400020403060006905100017000620460000038000090000")
	solve(&ans)
	loadSudoku("000602000400050001085010620038206710000000000019407350026040530900020007000809000")
	solve(&ans)
	loadSudoku("000900002050123400030000160908000000070000090000000205091000050007439020400007000")
	solve(&ans)
	loadSudoku("380000000000400785009020300060090000800302009000040070001070500495006000000000092")
	solve(&ans)
	loadSudoku("000158000002060800030000040027030510000000000046080790050000080004070100000325000")
	solve(&ans)
	loadSudoku("010500200900001000002008030500030007008000500600080004040100700000700006003004050")
	solve(&ans)
	loadSudoku("080000040000469000400000007005904600070608030008502100900000005000781000060000010")
	solve(&ans)
	loadSudoku("904200007010000000000706500000800090020904060040002000001607000000000030300005702")
	solve(&ans)
	loadSudoku("000700800006000031040002000024070000010030080000060290000800070860000500002006000")
	solve(&ans)
	loadSudoku("001007090590080001030000080000005800050060020004100000080000030100020079020700400")
	solve(&ans)
	loadSudoku("000003017015009008060000000100007000009000200000500004000000020500600340340200000")
	solve(&ans)
	loadSudoku("300200000000107000706030500070009080900020004010800050009040301000702000000008006")
	solve(&ans)
	fmt.Println("Problem 096:", ans)
}

// 初始化。0b xx1 1111 1111，xx为标志位 10 表示空，01 表示新确定（待用其更新其他关联格候选值），00表示以前确定
func loadSudoku(str string) {
	tryCell = 0
	chr := []byte(str)
	for i := 0; i < 81; i++ {
		if chr[i] == '0' {
			cell[i] = 0x5FF
		} else {
			cell[i] = 0x200 | (1 << (chr[i] - 49))
		}
	}
}

// 输出显示
func showBoard() {
	board := ""
	for i := range cell {
		//		if i%9 == 0 && i > 0 {
		//			board += "\n"
		//		}
		//		board += "["
		var j uint
		for j = 0; j < 9; j++ {
			if (cell[i] >> j & 1) == 1 {
				board += fmt.Sprintf("%d", j+49)
			}
		}
		//		board += "]"
	}
	fmt.Println(board)
}

// 计算有几个候选值。即二进制表示中包含几个1
func bitCount(i uint16) uint16 {
	i = i - ((i >> 1) & 0x5555)
	i = (i & 0x3333) + ((i >> 2) & 0x3333)
	i = (i + (i >> 4)) & 0x0f0f
	i = i + (i >> 8)
	return i & 0x3f
}

// 解数独主函数，更新候选值无变动就使用试填解法
func solve(ans *int) {
	var hasNew uint16
	for {
		hasNew = 1
		for hasNew&0xFF > 0 {
			hasNew = updateOptions()
		}
		if hasNew == 0x100 {
			break
		} else if hasNew == 0x200 {
			backForward()
		} else {
			tryOption()
		}
	}

	if !checkSudokus() {
		fmt.Println("[Error!]")
	} else {
		//showBoard()

		for j := 0; j < 9; j++ {
			if (cell[0] >> j & 1) == 1 {
				*ans += (j + 1) * 100
			}
			if (cell[1] >> j & 1) == 1 {
				*ans += (j + 1) * 10
			}
			if (cell[2] >> j & 1) == 1 {
				*ans += j + 1
			}
		}

	}
}

// 更新候选值
func updateOptions() uint16 {
	var hasNew, fixed uint16
	for i := range cell {
		if cell[i]&0x200 == 0x200 {
			opt := 0x9FF - cell[i]
			for j := 0; j < 20; j++ {
				cell[x[i][j]] &= opt
				if cell[x[i][j]]&0x1FF == 0 {
					return 0x200
				}
			}
			cell[i] ^= 0x200
			fixed++
		} else if cell[i] > 0x400 {
			var row, col, box uint16 = 0x600, 0x600, 0x600
			for j := 0; j < 8; j++ {
				row |= cell[x[i][j]]
				box |= cell[x[i][6+j]]
				col |= cell[x[i][12+j]]
			}
			if bitCount(cell[i] & ^row) == 1 {
				cell[i] &= ^row
			} else if bitCount(cell[i] & ^col) == 1 {
				cell[i] &= ^col
			} else if bitCount(cell[i] & ^box) == 1 {
				cell[i] &= ^box
			}
			if bitCount(cell[i]) == 1 {
				cell[i] |= 0x200
				hasNew++
			}
		} else {
			fixed++
		}
	}
	if fixed == 81 {
		return 0x100
	}
	return hasNew
}

func numberOfTrailingZeros(i uint8) uint8 {
	var y uint8
	var n uint8 = 7
	y = i << 4
	if y != 0 {
		n -= 4
		i = y
	}
	y = i << 2
	if y != 0 {
		n -= 2
		i = y
	}
	return n - uint8((i<<1)>>7)
}

// 设置尝试格
func tryOption() {
	for i := range cell {
		if cell[i] > 0x400 && bitCount(cell[i]) == 3 {
			for w, v := range cell {
				trials[tryCell*81+w] = v
			}
			var trialValue uint16 = 1 << numberOfTrailingZeros(uint8(cell[i]))
			trials[tryCell*81+i] = cell[i] ^ trialValue
			cell[i] = trialValue | 0x200
			tryCell++
			return
		}
	}
	for i := range cell {
		if cell[i] > 0x400 && bitCount(cell[i]) == 4 {
			for w, v := range cell {
				trials[tryCell*81+w] = v
			}
			var trialValue uint16 = 1 << numberOfTrailingZeros(uint8(cell[i]))
			trials[tryCell*81+i] = cell[i] ^ trialValue
			cell[i] = trialValue | 0x200
			tryCell++
			return
		}
	}
}

// 回退
func backForward() {
	if tryCell == 0 {
		panic("No solution!")
	}
	tryCell--
	for w := range cell {
		cell[w] = trials[tryCell*81+w]
		if cell[w] > 0x400 && bitCount(cell[w]) == 2 {
			cell[w] ^= 0x600
		}
	}
}
func checkSudokus() bool {
	for i := range cell {
		opt := ^cell[i]
		for j := 0; j < 20; j++ {
			cell[x[i][j]] &= opt
			if cell[x[i][j]] == 0 {
				return false
			}
		}
	}
	return true
}

// 提高速度，使用该索引表查询同行[0^7]同列[12^19]同块[6^13]的数字格
var x = [81][20]int{
	{3, 4, 5, 6, 7, 8, 1, 2, 10, 11, 19, 20, 9, 18, 27, 36, 45, 54, 63, 72},
	{3, 4, 5, 6, 7, 8, 0, 2, 9, 11, 18, 20, 10, 19, 28, 37, 46, 55, 64, 73},
	{3, 4, 5, 6, 7, 8, 0, 1, 9, 10, 18, 19, 11, 20, 29, 38, 47, 56, 65, 74},
	{0, 1, 2, 6, 7, 8, 4, 5, 13, 14, 22, 23, 12, 21, 30, 39, 48, 57, 66, 75},
	{0, 1, 2, 6, 7, 8, 3, 5, 12, 14, 21, 23, 13, 22, 31, 40, 49, 58, 67, 76},
	{0, 1, 2, 6, 7, 8, 3, 4, 12, 13, 21, 22, 14, 23, 32, 41, 50, 59, 68, 77},
	{0, 1, 2, 3, 4, 5, 7, 8, 16, 17, 25, 26, 15, 24, 33, 42, 51, 60, 69, 78},
	{0, 1, 2, 3, 4, 5, 6, 8, 15, 17, 24, 26, 16, 25, 34, 43, 52, 61, 70, 79},
	{0, 1, 2, 3, 4, 5, 6, 7, 15, 16, 24, 25, 17, 26, 35, 44, 53, 62, 71, 80},
	{12, 13, 14, 15, 16, 17, 10, 11, 1, 2, 19, 20, 0, 18, 27, 36, 45, 54, 63, 72},
	{12, 13, 14, 15, 16, 17, 9, 11, 0, 2, 18, 20, 1, 19, 28, 37, 46, 55, 64, 73},
	{12, 13, 14, 15, 16, 17, 9, 10, 0, 1, 18, 19, 2, 20, 29, 38, 47, 56, 65, 74},
	{9, 10, 11, 15, 16, 17, 13, 14, 4, 5, 22, 23, 3, 21, 30, 39, 48, 57, 66, 75},
	{9, 10, 11, 15, 16, 17, 12, 14, 3, 5, 21, 23, 4, 22, 31, 40, 49, 58, 67, 76},
	{9, 10, 11, 15, 16, 17, 12, 13, 3, 4, 21, 22, 5, 23, 32, 41, 50, 59, 68, 77},
	{9, 10, 11, 12, 13, 14, 16, 17, 7, 8, 25, 26, 6, 24, 33, 42, 51, 60, 69, 78},
	{9, 10, 11, 12, 13, 14, 15, 17, 6, 8, 24, 26, 7, 25, 34, 43, 52, 61, 70, 79},
	{9, 10, 11, 12, 13, 14, 15, 16, 6, 7, 24, 25, 8, 26, 35, 44, 53, 62, 71, 80},
	{21, 22, 23, 24, 25, 26, 19, 20, 1, 2, 10, 11, 0, 9, 27, 36, 45, 54, 63, 72},
	{21, 22, 23, 24, 25, 26, 18, 20, 0, 2, 9, 11, 1, 10, 28, 37, 46, 55, 64, 73},
	{21, 22, 23, 24, 25, 26, 18, 19, 0, 1, 9, 10, 2, 11, 29, 38, 47, 56, 65, 74},
	{18, 19, 20, 24, 25, 26, 22, 23, 4, 5, 13, 14, 3, 12, 30, 39, 48, 57, 66, 75},
	{18, 19, 20, 24, 25, 26, 21, 23, 3, 5, 12, 14, 4, 13, 31, 40, 49, 58, 67, 76},
	{18, 19, 20, 24, 25, 26, 21, 22, 3, 4, 12, 13, 5, 14, 32, 41, 50, 59, 68, 77},
	{18, 19, 20, 21, 22, 23, 25, 26, 7, 8, 16, 17, 6, 15, 33, 42, 51, 60, 69, 78},
	{18, 19, 20, 21, 22, 23, 24, 26, 6, 8, 15, 17, 7, 16, 34, 43, 52, 61, 70, 79},
	{18, 19, 20, 21, 22, 23, 24, 25, 6, 7, 15, 16, 8, 17, 35, 44, 53, 62, 71, 80},
	{30, 31, 32, 33, 34, 35, 28, 29, 37, 38, 46, 47, 36, 45, 0, 9, 18, 54, 63, 72},
	{30, 31, 32, 33, 34, 35, 27, 29, 36, 38, 45, 47, 37, 46, 1, 10, 19, 55, 64, 73},
	{30, 31, 32, 33, 34, 35, 27, 28, 36, 37, 45, 46, 38, 47, 2, 11, 20, 56, 65, 74},
	{27, 28, 29, 33, 34, 35, 31, 32, 40, 41, 49, 50, 39, 48, 3, 12, 21, 57, 66, 75},
	{27, 28, 29, 33, 34, 35, 30, 32, 39, 41, 48, 50, 40, 49, 4, 13, 22, 58, 67, 76},
	{27, 28, 29, 33, 34, 35, 30, 31, 39, 40, 48, 49, 41, 50, 5, 14, 23, 59, 68, 77},
	{27, 28, 29, 30, 31, 32, 34, 35, 43, 44, 52, 53, 42, 51, 6, 15, 24, 60, 69, 78},
	{27, 28, 29, 30, 31, 32, 33, 35, 42, 44, 51, 53, 43, 52, 7, 16, 25, 61, 70, 79},
	{27, 28, 29, 30, 31, 32, 33, 34, 42, 43, 51, 52, 44, 53, 8, 17, 26, 62, 71, 80},
	{39, 40, 41, 42, 43, 44, 37, 38, 28, 29, 46, 47, 27, 45, 0, 9, 18, 54, 63, 72},
	{39, 40, 41, 42, 43, 44, 36, 38, 27, 29, 45, 47, 28, 46, 1, 10, 19, 55, 64, 73},
	{39, 40, 41, 42, 43, 44, 36, 37, 27, 28, 45, 46, 29, 47, 2, 11, 20, 56, 65, 74},
	{36, 37, 38, 42, 43, 44, 40, 41, 31, 32, 49, 50, 30, 48, 3, 12, 21, 57, 66, 75},
	{36, 37, 38, 42, 43, 44, 39, 41, 30, 32, 48, 50, 31, 49, 4, 13, 22, 58, 67, 76},
	{36, 37, 38, 42, 43, 44, 39, 40, 30, 31, 48, 49, 32, 50, 5, 14, 23, 59, 68, 77},
	{36, 37, 38, 39, 40, 41, 43, 44, 34, 35, 52, 53, 33, 51, 6, 15, 24, 60, 69, 78},
	{36, 37, 38, 39, 40, 41, 42, 44, 33, 35, 51, 53, 34, 52, 7, 16, 25, 61, 70, 79},
	{36, 37, 38, 39, 40, 41, 42, 43, 33, 34, 51, 52, 35, 53, 8, 17, 26, 62, 71, 80},
	{48, 49, 50, 51, 52, 53, 46, 47, 28, 29, 37, 38, 27, 36, 0, 9, 18, 54, 63, 72},
	{48, 49, 50, 51, 52, 53, 45, 47, 27, 29, 36, 38, 28, 37, 1, 10, 19, 55, 64, 73},
	{48, 49, 50, 51, 52, 53, 45, 46, 27, 28, 36, 37, 29, 38, 2, 11, 20, 56, 65, 74},
	{45, 46, 47, 51, 52, 53, 49, 50, 31, 32, 40, 41, 30, 39, 3, 12, 21, 57, 66, 75},
	{45, 46, 47, 51, 52, 53, 48, 50, 30, 32, 39, 41, 31, 40, 4, 13, 22, 58, 67, 76},
	{45, 46, 47, 51, 52, 53, 48, 49, 30, 31, 39, 40, 32, 41, 5, 14, 23, 59, 68, 77},
	{45, 46, 47, 48, 49, 50, 52, 53, 34, 35, 43, 44, 33, 42, 6, 15, 24, 60, 69, 78},
	{45, 46, 47, 48, 49, 50, 51, 53, 33, 35, 42, 44, 34, 43, 7, 16, 25, 61, 70, 79},
	{45, 46, 47, 48, 49, 50, 51, 52, 33, 34, 42, 43, 35, 44, 8, 17, 26, 62, 71, 80},
	{57, 58, 59, 60, 61, 62, 55, 56, 64, 65, 73, 74, 63, 72, 0, 9, 18, 27, 36, 45},
	{57, 58, 59, 60, 61, 62, 54, 56, 63, 65, 72, 74, 64, 73, 1, 10, 19, 28, 37, 46},
	{57, 58, 59, 60, 61, 62, 54, 55, 63, 64, 72, 73, 65, 74, 2, 11, 20, 29, 38, 47},
	{54, 55, 56, 60, 61, 62, 58, 59, 67, 68, 76, 77, 66, 75, 3, 12, 21, 30, 39, 48},
	{54, 55, 56, 60, 61, 62, 57, 59, 66, 68, 75, 77, 67, 76, 4, 13, 22, 31, 40, 49},
	{54, 55, 56, 60, 61, 62, 57, 58, 66, 67, 75, 76, 68, 77, 5, 14, 23, 32, 41, 50},
	{54, 55, 56, 57, 58, 59, 61, 62, 70, 71, 79, 80, 69, 78, 6, 15, 24, 33, 42, 51},
	{54, 55, 56, 57, 58, 59, 60, 62, 69, 71, 78, 80, 70, 79, 7, 16, 25, 34, 43, 52},
	{54, 55, 56, 57, 58, 59, 60, 61, 69, 70, 78, 79, 71, 80, 8, 17, 26, 35, 44, 53},
	{66, 67, 68, 69, 70, 71, 64, 65, 55, 56, 73, 74, 54, 72, 0, 9, 18, 27, 36, 45},
	{66, 67, 68, 69, 70, 71, 63, 65, 54, 56, 72, 74, 55, 73, 1, 10, 19, 28, 37, 46},
	{66, 67, 68, 69, 70, 71, 63, 64, 54, 55, 72, 73, 56, 74, 2, 11, 20, 29, 38, 47},
	{63, 64, 65, 69, 70, 71, 67, 68, 58, 59, 76, 77, 57, 75, 3, 12, 21, 30, 39, 48},
	{63, 64, 65, 69, 70, 71, 66, 68, 57, 59, 75, 77, 58, 76, 4, 13, 22, 31, 40, 49},
	{63, 64, 65, 69, 70, 71, 66, 67, 57, 58, 75, 76, 59, 77, 5, 14, 23, 32, 41, 50},
	{63, 64, 65, 66, 67, 68, 70, 71, 61, 62, 79, 80, 60, 78, 6, 15, 24, 33, 42, 51},
	{63, 64, 65, 66, 67, 68, 69, 71, 60, 62, 78, 80, 61, 79, 7, 16, 25, 34, 43, 52},
	{63, 64, 65, 66, 67, 68, 69, 70, 60, 61, 78, 79, 62, 80, 8, 17, 26, 35, 44, 53},
	{75, 76, 77, 78, 79, 80, 73, 74, 55, 56, 64, 65, 54, 63, 0, 9, 18, 27, 36, 45},
	{75, 76, 77, 78, 79, 80, 72, 74, 54, 56, 63, 65, 55, 64, 1, 10, 19, 28, 37, 46},
	{75, 76, 77, 78, 79, 80, 72, 73, 54, 55, 63, 64, 56, 65, 2, 11, 20, 29, 38, 47},
	{72, 73, 74, 78, 79, 80, 76, 77, 58, 59, 67, 68, 57, 66, 3, 12, 21, 30, 39, 48},
	{72, 73, 74, 78, 79, 80, 75, 77, 57, 59, 66, 68, 58, 67, 4, 13, 22, 31, 40, 49},
	{72, 73, 74, 78, 79, 80, 75, 76, 57, 58, 66, 67, 59, 68, 5, 14, 23, 32, 41, 50},
	{72, 73, 74, 75, 76, 77, 79, 80, 61, 62, 70, 71, 60, 69, 6, 15, 24, 33, 42, 51},
	{72, 73, 74, 75, 76, 77, 78, 80, 60, 62, 69, 71, 61, 70, 7, 16, 25, 34, 43, 52},
	{72, 73, 74, 75, 76, 77, 78, 79, 60, 61, 69, 70, 62, 71, 8, 17, 26, 35, 44, 53}}
